Multicast technology makes it possible to send data from a single source to many recipients through a data network, without having to set up unicast communication, i.e. one-to-one individual communication between the source and each of the recipients. To that end the source sends data, in data packet form, to a single address associated to a multicast group to which the equipment interested in being recipients of said data sending can subscribe. This address, referred to as a multicast address or also as a multicast group address, is an IP (Internet Protocol) address chosen within a range that is reserved for multicast applications. The data packets which have been sent by the source to the multicast address are then replicated in the different network routers so that they can reach the recipients that have joined the multicast group.
The recipients which receive data in a multicast group are usually equipment connected to the data network by means of a proxy or a router.
Hereinafter, the common term host will be used to refer to said recipient equipment. A host can be, for example, a computer or a set-top box (digital signal decoder) connected to a television set.
When a host wants to receive the information sent by one or several sources of a multicast group, it sends to the closest router, or to an intermediate proxy, a subscription message to subscribe to said group so that the router transmits to it the data arriving through the data network and which has been sent by the sources of the multicast group. Likewise, when a host wishes to stop receiving data sending in the multicast group, it sends to the router or to the proxy an unsubscribe message to stop receiving them.
The messages exchanged between a host and the closest router to manage membership to a multicast group use the IGMP protocol (Internet Group Management Protocol) or the MLD (Multicast Listener Discovery) protocol, according to whether or not the router works with version 4 (IPv4) or version 6 (IPv6) of the IP protocol (Internet Protocol), respectively.
The routers exchange messages with one another for the purpose of defining the routing which allows efficiently routing the data from the sources to the hosts that have subscribed to a multicast group. To that end, the routers use specific protocols, including the very well known PIM-SM (Protocol Independent Multicast—Sparse Mode).
In summary, the routers receive from the hosts, in the form of IGMP/MLD messages, information specifying which multicast groups they want to receive traffic from, and they communicate with other routers, for example by means of the PIM-SM protocol, for the purpose of setting up a routing which takes the traffic requested by the hosts to such hosts.
All the mentioned protocols are defined and documented by the Internet Engineering Task Force (IETF).
The IGMP protocol version currently being used is IGMPv3, which is described in the RFC 3376 specifications published on line by the IETF (B. Cain et al., Engineering Task Force, Network Working Group, Request for Comments 3376, October 2002.
With regard to the MLD protocol, the version currently being used is MLDv2, which is described in the RFC 3810 specifications published on line by the IETF (R. Vida et al., Engineering Task Force, Network Working Group, Request for Comments 3810, June 2004.
The PIM-SM protocol used for the communication between routers is described in the RFC 4601 specifications published on line by the IETF (B. Fenner et al., Engineering Task Force, Network Working Group, Request for Comments 4601, August 2006.
Hereinafter, and in accordance with the common nomenclature in SSM technology, the sending of the source S from the multicast group G, where S is an IP address identifying the source sending the data and G is an IP address, within the range reserved for multicast groups, identifying the multicast group, is referred to as channel (S,G).
Hereinafter the expressions upstream and downstream will likewise be used to indicate relative locations from network equipment: the expression upstream relates to a location in the direction towards the multicast source and the expression downstream relates to a location in the opposite direction.
In the first multicast routing protocols, such as the DVMRP protocol (Distance Vector Multicast Routing Protocol) for example, the routers exchanged between one another messages called “DVMRP Route Reports” with information to build the multicast topology database. The multicast topology database is where the routers store the information from all the multicast routers existing in the network and how they are connected to one another. In the DVMRP protocol, each router sent these messages every 60 seconds.
The PIM-SM protocol works in a different manner. The PIM-SM routers do not send messages to create the multicast topology database, but rather they use the unicast database of the router to deduce from it the multicast topology database and they do so independently of the unicast protocol that the router uses. This is the reason for the name Protocol Independent Multicast. PIM-SM therefore does not depend on any specific unicast protocol and can create the multicast topology database in the routers independently of the unicast protocol that each router uses.
In the PIM-SM protocol the multicast topology database is stored in a table called MRIB (Multicast Routing Information Base) which is used, among other purposes, for deciding which router the JOIN/PRUNE messages should be sent to. These JOIN/PRUNE messages of the PIM-SM protocol, which are well-known by the person skilled in the art, are the messages sent by one PIM-SM router to another PIM-SM router to indicate that it wishes to receive multicast traffic (JOIN messages) or that it wishes to stop receiving multicast traffic (PRUNE messages). The multicast data are transmitted towards the router that has requested multicast traffic following the same way as the JOIN messages, but in the opposite direction.
A first drawback of the PIM-SM protocol is the delay in transmitting the PRUNE-type messages that one PIM-SM router sends to another PIM-SM router to indicate that it no longer wishes to keep receiving a specific multicast traffic. When a PIM-SM router receives a PRUNE-type message, for example PRUNE (S,G), it does not immediately stop transmitting the traffic from the multicast channel (S,G), but rather it waits for a specific time before it stops transmitting the multicast channel (S,G) through its network interface where it has received the PRUNE-type message. In the PIM-SM protocol default configuration, this wait time is 3 seconds. The reason for this wait time is that there may be other PIM-SM routers sharing a multiaccess network and it is possible that there is another PIM-SM router that wishes to keep receiving the multicast channel (S,G), therefore said router must send a JOIN(S,G) message immediately in order to cancel the effect of the previous PRUNE(S,G) message.
If the number of routers is high and there are thousands of users switching multicast channels, the consequence is that there is a huge amount of bandwidth occupied in the network due to the latency or delay in suppressing the transmission of unwanted multicast channels. The problem is considerably aggravated if the multicast channels (S,G) furthermore transmit video or IPTV channels requiring, for example, a bandwidth of between 4 Mbits/s in normal resolution and 20 Mbits/s in high resolution.
Section 4.3.3. of RFC 4601, “Reducing PRUNE Propagation Delay on LANs”, proposes a solution to the latency problem that consists of using the Hello messages that the PIM-SM routers use to exchange information with one another and to negotiate several parameters. Hello messages are used, for example, to negotiate whether or not there is a suppression of PIM-SM messages, the delay time in the PRUNE messages and other parameters. The PIM-SM routers send these Hello messages periodically through each network interface of the router in which the PIM-SM protocol is being executed, to a multicast address called “ALL-PIM-ROUTERS”. As a result of these Hello messages, each PIM-SM router knows the existence of other PIM-SM routers connected in each of its network interfaces. All the routers also store the configuration information for the other routers which has been exchanged by means of Hello messages.
However, the Hello messages used in the PIM-SM protocol do not transmit information on the topology of multicast routers. The PIM-SM router deduces this information based on unicast routing tables.
As previously stated, when a PIM-SM router receives a PRUNE(S,G)-type message it waits for a certain time to see if there is another router sending a JOIN(S,G) message canceling the first PRUNE message. The wait time is the sum of two variables called Effective_propagation_Delay and Effective_Override_Interval, which by default take the values of 0.5 seconds and 2.5 seconds, respectively. The reason for using this sum of two variables as a delay is the following: if there is a router R1 that is receiving traffic of the multicast channel (S,G) from a router R2, and router R1 sees that another router R3 sends a PRUNE(S,G) message, router R1 must send a JOIN(S,G)-type message to router R2 to cancel the effect of the PRUNE(S,G) message before the Effective_Override_Interval time. Since the Effective_Override_Interval is always less than the sum of Effective_Override_Interval and Effective_propagation_Delay, the JOIN(S,G) message of router R1 will reach router R2 before router R2 stops sending traffic of the multicast channel (S,G).
The solution proposed in RFC 4601 for reducing the latency time consists of the fact that PIM-SM routers use the Hello messages to reduce the values of the Effective_propagation_Delay and Effective_Override_Interval variables. To that end, all PIM-SM routers announce their own Propagation_Delay and Override_Interval parameters in the Hello messages. These parameters are contained in the Hello messages in a data block called LAN_PRUNE_Delay. When all the routers executing the PIM-SM protocol in a network have sent Hello messages including the LAN_PRUNE_Delay data block, all the routers connected to one and the same multiaccess network use as Effective_propagation_Delay and Effective_Override_Interval values the maximum values of the Propagation_Delay and Override_Interval parameters, respectively, that have been announced by said routers in the Hello messages.
However, this mechanism has several limitations. In the first place, the RFC 4601 indicate that if the Effective_propagation_Delay and Effective_Override_Interval variables take very low values, it is possible that, in following with the previous example, router R2 suppresses the traffic of channel (S,G) before router R1 has time to send its JOIN message or before router R2 has time to process said message. To prevent this problem, RFC 4601 recommend not lowering the values of these variables too much. This is a serious limitation of this latency reduction mechanism.
Furthermore, another limitation or problem that this latency reduction mechanism has is that it is necessary for all the routers executing the PIM-SM protocol in a network to send messages including the LAN_PRUNE_Delay data block. If there is a router that does not include this data block in its Hello messages, this latency reduction mechanism can no longer be used and the Effective_propagation_Delay and Effective_Override_Interval variables take their default values, which are 2.5 seconds and 0.5 seconds respectively, in all the routers of the multiaccess network, therefore causing a latency of 3 seconds in each router.
In addition, at the end of the mentioned section 4.3.3 of RFC 4601 relating to latency reduction, it is explained that it is possible for an Upstream PIM-SM router to have individual control or tracking of the multicast traffic requests of several downstream routers. Though it does not explain how to implement said individual tracking or what utility it has, it does indicate that to do so it is essential for all the routers of the same multiaccess network to first agree to cancel the message suppression. The mentioned section 4.3.3 of RFC 4601 even includes the code that can be used to check that all the routers have agreed to cancel the message suppression.
A second problem affecting the PIM-SM protocol is the complexity of the JOIN message suppression mechanism. Basically, JOIN message suppression consists of if a downstream router R1 sees that another downstream router R2 sends a JOIN message requesting the same multicast traffic that it was going to request, said router R1 can suppress its own JOIN message, since it is sufficient that the upstream router receives a single request to transmit the requested multicast traffic.
In the latest version of the IGMP protocol multicast (IGMPv3 version), by means of which hosts request multicast traffic from a router, the message suppression, which existed in the previous IGMP versions, has been canceled. In contrast, in the PIM-SM protocol, by means of which a router requests multicast traffic from another router, message suppression still exists. In fact, message suppression is the default configuration to be applied according to RFC 4601. There is a configuration option available so that message suppression is not carried out, but it is applied only in specific circumstances and requires a complex implementation.
The message suppression mechanism that is applied in the PIM-SM protocol, according to RFC 4601, is very complicated. The message suppression cancellation mechanism is also very complicated according to RFC 4601. Therefore any modification of the PIM-SM protocol relating to message suppression is very complicated. This probably explains the lack of investigation for improvements in the PIM-SM protocol relating to message suppression. Additionally, the end of mentioned section 4.3.3 of RFC 4601 indicates that in order to perform individual tracking of the multicast traffic requested by each downstream router, it is necessary to cancel the message suppression. According to RFC 4601, if there are routers suppressing messages it is not possible to perform individual tracking of the multicast traffic requested by each router.
The following description illustrates the complexity of the message suppression mechanism and the conditions for canceling said message suppression, according to RFC 4601.
To explain the message suppression mechanism a person skilled in the art has to analyze and understand in detail the state machine called upstream (S,G), by means of which RFC 4601 specify the operation of the upstream sending of JOIN(S,G)-type messages. This state machine is shown in table form in section 4.5.7 “Sending (S,G) Join/Prune messages” of RFC 4601.
Each upstream state machine (S,G) is independent for each network interface of the router and for each multicast channel (S,G) and has only two states: the Not_Joined state, which means that the router does not need to receive the multicast channel (S,G) through said network interface, and the Joined state, which means that the router needs to receive the multicast channel (S,G) through said network interface.
If the state machine is in the Not_Joined state, and therefore the router is not receiving the multicast channel (S,G), and a “JoinDesired(S,G)→true” event occurs, indicating that the router has received a request for traffic of channel (S,G) from another downstream router, the state machine of the router executes the following actions: switching the state to Joined, sending a JOIN(S,G) message to another upstream router appearing in its MRIB table as suitable for sending it traffic of channel (S,G), and initializing a timer called Join_Timer at an initial value called t_periodic.
In the Joined state, when the “Timer Expires” event occurs, indicating that the Join_Timer has reached zero, the router sends (Send Join(S,G)) a new JOIN(S,G) message and reinitializes the Join_Timer at the t_periodic value.
Therefore, in the Joined state the router periodically sends the JOIN(S,G) messages again to keep receiving traffic of the multicast channel (S,G).
When the “See Join(S,G) to RPF′(S,G)” event occurs, indicating that router has seen in the multiaccess network it is connected to that another router has sent a message similar to the JOIN(S,G) message that it has to send when the Join_Timer reaches zero, the router increases the Join_Timer value to delay the sending of its own JOIN(S,G) message. This is explained in greater detail on page 74 of RFC 4601, indicating that if the Join_Timer has a value that is less than a variable called t_joinsuppress, then said Join_Timer is initialized with the value of this t_joinsuppress variable. However, if the Join_Timer has a value that is greater than the t_joinsuppress variable, then the Join_Timer is not modified.
Therefore, the message suppression mechanism of the PIM-SM protocol consists of increasing the value of the Join_Timer controlling the periodic sending of JOIN(S,G) messages. Since the Join_Timer is increased up to the t_joinsuppress value every time the router sees a JOIN(S,G) message of another router in the multiaccess network, the Join_Timer is periodically reinitialized at the t_joinsuppress value and never reaches zero. This is what makes the router not send its own JOIN(S,G) message, i.e. it suppresses its own periodic JOIN(S,G) message as long as there is another router in the same multiaccess network that is sending an equivalent JOIN(S,G) message.
Message suppression in the PIM-SM protocol has been explained up to this point. Explained below is how the mechanism canceling said message suppression works.
The mechanism to cancel message suppression in the PIM-SM protocol, as deduced from RFC 4601, consists of making the value of the t_joinsuppress variable zero. When the router sees a JOIN(S,G) message it checks to see if the Join_Timer is less than the t_joinsuppress variable, which is equal to zero, which obviously never occurs, and said Join_Timer is left unmodified. The router thus sends its own JOIN(S,G) message when its Join_Timer, which is not modified by the messages of the other routers, reaches zero.
The t_joinsuppress variable takes the lowest value between the value of another variable called t_suppressed and a parameter called holdtime which is transmitted in the JOIN(S,G) messages and indicates for how much time the router that has sent the JOIN(S,G) message wishes to be receiving the channel (S,G). The t_suppressed variable takes a different value depending on whether or not message suppression is enabled. There is a function called Suppression_Enabled(I) which is specific for each network interface I and returns the value TRUE if message suppression is enabled, and the value FALSE if message suppression is cancelled:
If the Supression_Enabled(I) function returns a TRUE value, then the t_suppressed variable takes a random value within the range [1,1*t_periodic; 1,4*t_periodic], where t_periodic is a variable taking the value of 60 seconds by default.
If the Supression_Enabled(I) function returns the FALSE value, the t_suppressed variable is zero, and the t_joinsuppress variable is also zero, taking the lowest value between t_suppressed and the holdtime parameter. Modifying the Join_Timer when the Supression_Enabled(I) function returns a FALSE value is thus prevented and each router thus sends its periodic JOIN(S,G) messages without taking into account the JOIN(S,G) messages the other routers send, whereby canceling message suppression.
This message suppression cancellation mechanism defined in RFC 4601 is unnecessarily complicated. It is also inefficient because if the Supression_Enabled(I) function returns a FALSE value, before having made the decision of whether or not to modify the Join_Timer, the router will have checked two times to see if a positive quantity is less tan zero, something which cannot happen.
Since the PIM-SM protocol is a complex protocol, programmers designing applications implementing said protocol follow RFC 4601 specifications in the most exact manner possible to prevent finding new design problems that are not provided for in said specifications. As a result, applications implementing the PIM-SM protocol have the previously explained limitations. These limitations, along with the complexity involved with message suppression in the PIM-SM protocol, are the reasons that no satisfactory solution to the latency problem in the PIM-SM protocol has been developed up until now.